package q968_minCameraCover;

import CommonClass.Common.TreeNode;

public class Solution {
    int cameras = 0;
    public int minCameraCover(TreeNode root) {
        if(dfs(root) == 0) cameras++;
        return cameras;
    }

    /*
    考虑这样一个问题 如何确定哪些节点要装摄像头？
    我们发现题⽬示例中的摄像头都没有放在叶⼦节点上
    这是很重要的⼀个线索，摄像头可以覆盖上中下三层，如果把摄像头放在叶⼦节点上，就浪费的⼀层的覆盖。
    所以把摄像头放在叶⼦节点的⽗节点位置，才能充分利⽤摄像头的覆盖⾯积。
    那么为什么不从头结点开始看起，而从叶⼦节点看呢？
    因为头结点放不放摄像头也就省下⼀个摄像头， 叶⼦节点放不放摄像头省下了的摄像头数量是指数阶别的
    所以我们要从下往上看
    局部最优：让叶⼦节点的⽗节点安摄像头，所⽤摄像头最少
    整体最优：全部摄像头数量所⽤最少

    所以从下往上遍历 我们需要使用后序遍历
    在遍历的过程中 我们还需要确定不同节点是怎样的一种状态
    不妨这样考虑：
    0 该节点当前没有被覆盖到
    1 该节点是一个摄像头节点
    2 该节点被摄像头节点视野所覆盖

    对于dfs 首先考虑终止条件：空节点应该认为是怎样的节点？
    我们只需要考虑它是不同值所带来的后果即可 如果空节点是0 那么叶子节点的两侧都是没有被覆盖到
    理论上来说叶子节点就应该装摄像头 显然不符合逻辑
    而显然空节点也不应该是一个摄像头节点 例如如果只有一个节点 它两侧节点都是空节点 那么它就被摄像头节点覆盖到了
    所以它只能是已被覆盖的节点 所以dfs至空节点应该返回2

    通过左右根的顺序 分别获取了left和right的值后 我们开始处理中间节点
    对于一个节点 如果它左右只要有一个没有被覆盖到的 显然它应该装摄像头 返回1 并cam++
    如果它左右只要有一个摄像头 那么它就被覆盖了 返回2
    除此之外 就只有左右都是被覆盖的 我们就是为该节点没有被覆盖 返回0
     */
    private int dfs(TreeNode root) {
        if (root == null) {
            return 2;
        }

        int left = dfs(root.left);
        int right = dfs(root.right);

        if (left == 0 || right == 0) {
            cameras++;
            return 1;
        }

        if (left == 1 || right == 1) {
            return 2;
        }

        return 0;
    }
}
